home *** CD-ROM | disk | FTP | other *** search
/ Workbench Add-On / Workbench Add-On - Volume 1.iso / Dev / TileForth / lib / queues.f83 < prev    next >
Text File  |  1995-08-25  |  4KB  |  136 lines
  1. \
  2. \  DOUBLE LINKED LISTS
  3. \
  4. \  Copyright (C) 1988-1990 by Mikael R.K. Patel
  5. \
  6. \  Computer Aided Design Laboratory (CADLAB)
  7. \  Department of Computer and Information Science
  8. \  Linkoping University
  9. \  S-581 83 LINKOPING
  10. \  SWEDEN
  11. \
  12. \  Email: mip@ida.liu.se
  13. \
  14. \  Started on: 30 June 1988
  15. \
  16. \  Last updated on: 23 July 1990
  17. \
  18. \  Dependencies:
  19. \       (forth) forth, structures, blocks
  20. \
  21. \  Description:
  22. \       Allows definition and basic manipulation of queue data structures.
  23. \
  24. \  Copying:
  25. \       This program is free software; you can redistribute it and\or modify
  26. \       it under the terms of the GNU General Public License as published by
  27. \       the Free Software Foundation; either version 1, or (at your option)
  28. \       any later version.
  29. \
  30. \       This program is distributed in the hope that it will be useful,
  31. \       but WITHOUT ANY WARRANTY; without even the implied warranty of
  32. \       MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  33. \       GNU General Public License for more details.
  34. \
  35. \       You should have received a copy of the GNU General Public License
  36. \       along with this program; see the file COPYING.  If not, write to
  37. \       the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. 
  38.  
  39. .( Loading Queues definitions... ) cr
  40.  
  41. #include structures.f83
  42. #include blocks.f83
  43.  
  44. blocks structures queues definitions
  45.  
  46. struct.type QUEUE ( -- )
  47.   ptr +succ ( queue -- addr) private
  48.   ptr +pred ( queue -- addr) private
  49. struct.init ( queue -- )
  50.   dup over +succ ! dup +pred !
  51. struct.end 
  52.  
  53. : succ ( queue -- succ)
  54.   +succ @
  55. ;
  56.  
  57. : pred ( queue -- pred)
  58.   +pred @
  59. ;
  60.  
  61. #ifundef ?empty-queue    ( Check if the kernel supports queues)
  62.  
  63. : ?empty-queue ( queue -- bool)
  64.   dup +succ @ =             ( Pointer to itself)
  65. ;
  66.  
  67. : enqueue ( item queue -- )
  68.   2dup +pred @ swap +pred !        ( item.pred = queue.pred)
  69.   2dup swap +succ !            ( item.succ = queue)
  70.   2dup +pred @ +succ !            ( queue.pred.succ = item)
  71.   +pred !                 ( queue.pred = item)
  72. ;
  73.  
  74. : dequeue ( item -- )
  75.   dup +succ @ over +pred @ +succ !    ( item.pred.succ = item.succ)
  76.   dup +pred @ over +succ @ +pred !    ( item.succ.pred = item.pred)
  77.   dup over +succ !            ( item.succ = item)
  78.   dup +pred !                ( item.pred = item)
  79. ;
  80.  
  81. #then
  82.  
  83. : size-queue ( queue -- num)
  84.   0 swap dup >r                ( Save pointer to queue header)
  85.   begin
  86.     swap 1+ swap +succ @        ( Increment size and step to next)
  87.     dup r@ =                ( Is this the last element?)
  88.   until
  89.   r> 2drop                ( Drop parameters and return size)
  90. ;
  91.  
  92. : map-queue ( queue block[item -- ] -- )
  93.   over >r                ( Save pointer to queue header)
  94.   begin
  95.     over +succ @ >r            ( Save pointer to next item)
  96.     dup >r                ( Save block on return stack)
  97.     call                ( Call the block with the item)
  98.     2r> tuck                ( Restore the parameters)
  99.     r@ =                ( Check if end of queue)
  100.   until
  101.   r> drop 2drop             ( Drop all temporary parameters)
  102. ;
  103.  
  104. : ?map-queue ( queue block[item -- bool] -- )
  105.   over >r                ( Save pointer to queue header)
  106.   begin
  107.     over +succ @ >r            ( Save pointer to next item)
  108.     dup >r                ( Save block on return stack)
  109.     call                ( Call the block with the item)
  110.     if 2r> true                ( Exit the iteration)
  111.     else
  112.       2r> tuck                ( Restore the parameters)
  113.       r@ =                ( Check if end of queue)
  114.     then
  115.   until
  116.   r> drop 2drop             ( Drop all temporary parameters)
  117. ;
  118.  
  119. : ?member-queue ( element queue -- bool)
  120.   dup >r                ( Save pointer to queue header)
  121.   begin
  122.     2dup =                ( Is this the element?)
  123.     if 2drop r> drop true exit then    ( Well drop the parameters and return)
  124.     +succ @ dup r@ =            ( Step to the next. Last element?)
  125.   until
  126.   r> drop 2drop false
  127. ;
  128.  
  129. : .queue ( queue -- )
  130.   ." queue#" dup .            ( Print address of queue)
  131.   ." succ: " dup +succ @ .        ( Print successor)
  132.   ." pred: " +pred @ .            ( Print predecessor)
  133. ;
  134.  
  135. forth only
  136.